71. Выражение из цифр

Достаточно известная задача по математике: как при помощи пяти цифр 2, знаков арифметических действий и скобок записать число 7?

Это можно сделать так: (2 + 2 * 2) + 2 / 2, и так: 22 / 2 – 2 * 2 или так: 2 * (2 + 2) – 2 / 2.

А какое наименьшее натуральнее число m нельзя задать таким способом, использовав n цифр d?

Примечание: Деление выполняется без остатка.

Вход. В одной строке записаны натуральные числа n и d (1 ≤ n ≤ 7, 1 ≤ d ≤ 9).

Выход. Вывести число m – наименьшее число, которое нельзя задать арифметическим выражением, используя n цифр d.

Пример входа	Пример выхода
3 2	4

РЕШЕНИЕ

математика

Анализ алгоритма

Пусть множество s[i] хранит все значения, которые можно получить в результате арифметических действий, используя i цифр d. Изначально положим в s[i] число, состоящее из i цифр d. Перед числом может также находиться унарный минус. Поэтому если d = 2, то инициализируем s[1] = (-2, 2), s[2] = (-22, 22), s[3] = (-222, 222), s[4] = (-2222, 2222), … .

Рассмотрим, как заполнить числами множество s[i]. Для этого следует рассмотреть все выражения, состоящие из j (1 ≤ j ≤ i / 2) цифр d, а также все выражения, состоящие из i – j цифр d, совершить над ними все возможные арифметические действия и результат положить в s[i]. То есть мы перебираем все числа x из s[j], перебираем все числа y из s[i – j], совершаем над ними все четыре арифметические действия (x + y, x – y, y – x, x * y, x / y, y / x) и результат кладем в s[i]. Операцию деления x / y можно совершить только если y ≠ 0 и x делится нацело на y.

Ответом на задачу будет наименьшее натуральное число, отсутствующее во множестве s[n].

Пример

Пусть n = 3, d = 2. Тогда множества будут иметь вид:

Наименьшим натуральным числом, отсутствующим в s[3], является 4.

Реализация алгоритма

Объявим массив множеств s и итераторы.

set<int> s[10];

set<int>::iterator it1, it2;

Читаем входные данные.

scanf("%d %d",&n,&d);

Заносим в s[i] число, состоящее из i цифр d. Заносим как положительное число, так и соответствующее ему отрицательное.

val = 0;

for (i = 1; i <= n; i++)

{

val = 10 * val + d;

s[i].insert(val);

s[i].insert(-val);

}

Строим множество s[i].

for (i = 2; i <= n; i++)

for (j = 1; j + j <= i; j++)

Перебираем все элементы x из s[j].

for (it1 = s[j].begin(); it1 != s[j].end(); it1++)

Перебираем все элементы y из s[i – j].

for (it2 = s[i - j].begin(); it2 != s[i - j].end(); it2++)

{

int x = *it1, y = *it2;

Совершаем все возможные операции над аргументами x и y, результат заносим в s[i]. Поскольку мы работаем со множествами, то дублирующие элементы сохраняться не будут.

s[i].insert(x + y);

s[i].insert(x * y);

if (y != 0 && x % y == 0) s[i].insert(x / y);

if (x != 0 && y % x == 0) s[i].insert(y / x);

s[i].insert(x - y);

s[i].insert(y - x);

}

Ищем наименьшее число res, которого нет во множестве s[n].

res = 1;

while(s[n].find(res) != s[n].end()) res++;

printf("%d\n",res);